#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    long long ans = 0;
    int targ;
    int findTargetSumWays(vector<int>& nums, int target) {
        targ = target;
        dfs(nums, 0, 0);
        return ans;
    }

    void dfs(vector<int>& nums, int sum, int posi)
    {
        if (posi == nums.size()) {
            if (sum == targ) ans++;
            return;
        }
        dfs(nums, sum + nums[posi], posi + 1);
        dfs(nums, sum - nums[posi], posi + 1);
    }
};

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int len = nums.size();
        int sum = 0;
        int dig_zero = 0;
        for (auto& e : nums) {
            sum += e;
            if (e == 0) dig_zero++;
        }

        if ((target + sum) % 2 != 0) return 0;
        int V = (target + sum) / 2;
        if (V < 0) return 0;
        // if(V == 0) return 1;
        vector<vector<int>> dp(len + 1, vector<int>(V + 1, 0));

        // for(int j = 1;j <= V;j++)
        //     dp[0][j] = -1;
        for (int i = 0; i <= len; i++)
            dp[i][0] = 1;

        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1] && nums[i - 1] && dp[i - 1][j - nums[i - 1]]) {
                    // dp[i][j] = dp[i - 1][j - nums[i - 1]] == -1 ? 1 : dp[i][j] + 1;
                    dp[i][j] += dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        int ans = dp[len][V];

        // cout << dig_zero << endl;
        for (int i = 0; i < dig_zero; i++) {
            ans *= 2;
        }

        // for(int i = 0;i <= len;i++){
        //     for(int j = 0;j <= V;j++){
        //         cout << dp[i][j] << " ";
        //     }
        //     cout << endl;
        // }

        return ans;
    }
};

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (auto e : nums) sum += e;
        int aim = (sum + target) / 2;
        if (aim < 0 || (sum + target) % 2) return 0;
        int len = nums.size();
        vector<int> dp(aim + 1);
        dp[0] = 1;
        for (int i = 1; i <= len; i++) {
            for (int j = aim; j >= nums[i - 1]; j--) {
                dp[j] += dp[j - nums[i - 1]];
            }
        }
        return dp[aim];
    }
};